/*
 * @lc app=leetcode id=44 lang=cpp
 *
 * [44] Wildcard Matching
 */
class Solution {
public:
    bool isMatch(string s, string p) {
        int slen = s.length();
        int plen = p.length();

        vector<vector<bool>> memo(slen+1, vector<bool>(plen+1, false));
        memo[0][0] = true;
        for (int i=1; i<=plen; i++) {
            memo[0][i] = memo[0][i-1] && p[i-1] == '*';
        }

        for (int i=1; i<=slen; i++) {
            for (int j=1; j<=plen; j++) {
                if (s[i-1] == p[j-1]) {
                    memo[i][j] = memo[i-1][j-1];
                } else {
                    if (p[j-1] == '?') {
                        memo[i][j] = memo[i-1][j-1];
                    } 
                    if (p[j-1] == '*') {
                        memo[i][j] = memo[i][j-1] || memo[i-1][j];
                    } 
                }
            }
        }

        return memo[slen][plen];
        
    }
};

